Problem :
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.

Example 1 :

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2 :

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3 :

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

核心思維 :

1. 設定儲存解碼後的字串、暫存的字串和括號前的乘數
2. 設定堆疊儲存乘數和遍歷過程中的結果
3. 遍歷字串中的字符

• 若字符為數字則更新乘數
• 若字符為 ’ [ ’，將當前的結果和乘數放進儲存解碼後字串的結果當中，並將乘數和結果重置
• 若字符為’ [ ‘，將目前結果儲存並依照乘數重複當前的結果，並將結果和暫存連接，接著把乘數移出並將 ' [ ' 前的字串添加至結果中
• 若字符為字母則將字母新增至目前的結果當中

4. 回傳解碼完的字串

程式碼 :

class Solution {
public:
    string decodeString(string s) {
        //指定m為輸入字串的大小
        const int m = s.size();
        //儲存解碼後的字串
        string result = "";
        //暫存字串
        string temp = "";
        //儲存'['前的乘數
        int mul = 0;

        //使用堆疊來儲存乘數和遍歷過程中的結果
        stack<int> num;
        stack<string> st;
        
        //遍歷字串中的字符
        for(int i = 0; i < m; i++){
            //若字符為數字
            if(s[i] >= '0' && s[i] <= '9'){
                //更新乘數
                mul = mul*10 + (s[i]-'0');
            }
            //若子符為'['
            else if(s[i]=='['){
                //將當前的結果和乘數放進儲存解碼後字串的結果當中
                st.push(result);
                num.push(mul);
                //將乘數和結果重置
                mul = 0;
                result = "";
            }
            //若字符為']'
            else if(s[i]==']'){
                //儲存目前結果
                temp = result;
                //依照乘數重複當前結果
                for(int j=1; j < num.top(); j++){
                    //將結果和暫存連接
                    result=result+temp;
                }
                //將乘數移出並將'['前的字串添加至結果中
                num.pop();
                result = st.top() + result;
                st.pop();
            }
            //若字符為字母則將字母新增至目前的結果當中
            else{
                result.push_back(s[i]);
            }
        }
        //回傳解碼完的字串
        return result;
    }
};

結論 :

這題的目標是將題目給的編碼字串回傳成解碼後的字串，需要解決帶有括號和重複次數的字串解碼問題，透過遍歷字串中的字符來決定括號、數字或是字母添加至哪一個字串，在經過遍歷後將字符數量按照乘數進行輸出，得到解碼完的字串，利用堆疊可以有條理的將字符排好並按照數量進行輸出。